package com.vint.leetcode;

import com.vint.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/*
 * 1. TODO
 * 2. medium
 * 3. tree, 递归和抚今追昔
 * 判断是否有从根到叶子的路径，使得路径之和为给定的值, 如果存在，则把路径打印出来
 */
public class Leetcode113 {
	public List<List<Integer>> pathSum(TreeNode root, int sum) {
		List<List<Integer>> ret = new ArrayList<>();
		if(null==root) return ret;
		helpPath(root, sum, null);
		return ret;
	}
	public boolean helpPath(TreeNode root, int num, List<Integer> ret) {
		if(null == root) return false;
		if(root.right==null&&root.left==null&&root.val == num) {
			ret.add(root.val);
			return true;
		}
		boolean left = helpPath(root.left, num - root.val, ret);
		boolean right = helpPath(root.right, num - root.val, ret);
		if(root.left==null&& right) {
			return true;
		}
		if(root.right==null&& left){
			return true;
		}
		return false;
	}
}
